package nowcoder.huawei;

import java.io.FileReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author wuguojian
 * @description
 * @date
 * https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
 * 这里有最短路径要求，所以只能用BFS。
 **/
public class HJ43 {
    private final static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    private final static Point startPoint = new Point(0, 0);
    private static Point endPoint;
    private static Stack<Point> stack = new Stack<Point>();
    private static Queue<Point> queue = new LinkedList<Point>();


    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(new FileReader("input/nowcoder_huawei/HJ43.txt"));
//        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            queue.clear();
            int y = in.nextInt();
            int x = in.nextInt();
            endPoint = new Point(x-1, y-1);
            int[][] map = new int[y][x];
            for (int n = 0; n < y; n++) {
                for (int m = 0; m < x; m++) {
                    map[n][m] = in.nextInt();
                }
            }
            Point start = new Point(0, 0, null);
            queue.offer(start);
            while(!queue.isEmpty()) {
                if(search(map, queue)){
                    break;
                }
            }
            while(!stack.isEmpty()){
                Point p = stack.pop();
                System.out.println("(" + p.y + "," + p.x + ")");
            }
        }
    }

    private static boolean search(int[][] map, Queue<Point> queue) {
        Point point = queue.poll();
        if (point == null || point.x < startPoint.x || point.y < startPoint.y) {
            return false;
        }
        if (point.y > endPoint.y || point.x > endPoint.x) {
            return false;
        }
        if (map[point.y][point.x] == 1) {
            return false;
        }
        // 到达终点
        if (point.x == endPoint.x && point.y == endPoint.y) {
            print(point);
            return true;
        }
        // 搜索过的标志位1
        map[point.y][point.x] = 1;
        for (int[] d : dir) {
            queue.offer(new Point(point.x + d[0], point.y + d[1], point));
        }
        search(map, queue);
        return false;
    }

    private static void print(Point point) {
        if(null == point){
            return;
        }
        stack.push(point);
        print(point.father);
    }

    static class Point {
        int x;
        int y;
        Point father;

        public Point() {
        }

        public Point(int x, int y, Point father) {
            this.x = x;
            this.y = y;
            this.father = father;
        }

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
